COMMENT ⊗   VALID 00007 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.NEWSEC INTRODUCTION
C00008 00003	.NEWSEC (GOALS,MANIPULATOR CONTROL)
C00015 00004	.NEWSS (THE RUNTIME SYSTEM,RUNTIME)
C00019 00005	.NEWSS (PROGRAMMING AIDS,PROGRAMMING AIDS)
C00022 00006	.NEWSS (SOPHISTICATED USE OF WORLD MODEL INFORMATION,WORLD MODEL)
C00029 00007	.NEWSEC (GENERAL SYSTEM OUTLINE,HARDWARE)
C00039 ENDMK
C⊗;
.NEWSEC INTRODUCTION

	The development  of mechanical  manipulators during the  Late
Middle  Ages of  1948 soon  led  to the  realization that  most tasks
require position  and  force  feedback.   For  the  last  ten  years,
computers have  been used  as a  controlling agent.  This has  led to
sophisticated   servo   programs   which   periodically   compute  a
controlling signal from comparison of current manipulator
status against the planned status.

	Elementary  languages  have been  built  for  the purpose  of
automating tasks  more lengthy  than simple  motions. These languages
have  much  the  flavor of  assembly  languages;  primitive  commands
involve  those necessary for  planning various kinds  of motions, for
controlling the  execution of  the computed  plans,   and for  simple
response to error conditions.

	APT is  one highly  successful system  for the automation  of
parts-machining  tasks.    It  provides  open-loop  control of  metal
cutting machines and allows precision cutting along curved  lines and
accurate  workpiece  positioning.    The principal  failings  of  APT
involve  its poverty of descriptive  ability for complicated motions,
the  resulting  limitation  on  the  type  of  tasks   which  it  can
accomplish, and its restriction to metal cutting machines.

	Another example  of a system for  manipulator control is WAVE
at Stanford.  It includes two Scheinman electrical arms  and software
for  preparing  moderately  complex   plans.    The  most  impressive
accomplishment of  this system has been the assembly of a water pump,
which was  done with  one arm,   and  optionally made  use of  visual
feedback.   Further  achievements have  included a  primitive two-arm
task:  the  assembly  of  a  hinge.    WAVE  currently  can   produce
independent plans for the two arms.  The only form of coordination is
achieved by halting one arm and starting the other one.  The world model
contained  in the  system is quite  limited: A  small
number of hand  positions can be remembered; each  of these positions
can be  associated with an "offset" between planned position and real
position.  This information  is obtained during the  actual execution
of  a plan, and  allows run-time  modification of  trajectories.   The
sophistication of the  control structure is  also limited; there are  only
simple jumps,   including conditionals on  error states.   When a
plan fails  due to excessive requests on  hardware ability,  the user
may request the  continuation of the  plan.  WAVE  also has a  clumsy
interface with SAIL, which is a high-level Algol-like language; thus,
in principal, it can take advantage of SAIL's algebraic power.

	None  of the currently available task-automation languages is
capable of  efficiently sequencing tasks  or planning other  strategy
for  the  execution  of a  task;  they  only  can translate  explicit
instructions into machine-executable form. In this sense they can  be
thought of as  "assembly languages"; some  of them are  rather fancy,
with  a macro  facility,   a few  named variables,   and  some simple
arithmetic,  but none can be called a high-level language.

	The availability  of  new  types of  hardware  (for  example,
force-sensing wrists) and  the increasing complexity of  the tasks we
wish to perform, as well as the recognized failings of WAVE, have led
us to the design of a new hand language, which is called  HAL.  It is
a  very high  level language  for the  specification  of manipulatory
tasks (especially  assembly tasks)  in a  world of  several arms  and
other devices.  The following pages contain a description of HAL.

.NEWSEC (GOALS,MANIPULATOR CONTROL)
.<<UNDER REVISION>>

	A  full  language  for planning  manipulatory  tasks  of  the
complexity required  for assembly needs many  features, some of which
do not exist in any current system.  We have identified the following
interrelated goals.

.NEWSS (HIGH LEVEL LANGUAGE FOR MANIPULATOR CONTROL,MANIPULATOR CONTROL)

The datatypes available should include those necessary to refer to
one-dimensional measures (like distance, time, mass) and three-dimensional
measures (like directed distance, locations, orientations).
Arithmetic operators should be available for not only the standard
scalar operations like multiplication and addition, but also for
such operations as rotation and translation.

We want to write entire programs in a natural manner.  The
machine-language  aspect of  current manipulation languages  makes it
cumbersome to write  long programs in  any structured  way.  What  is
desired is  a language which  lends itself  to a more  systematic and
perspicuous programming style. Algol-like control structures would be
a vast improvement over assembly-like straight code with jumps.

Simultaneous execution  of  several processes  should  be
available. A general mechanism for simultaneity is desired.


Experience   with   WAVE  has   shown  that   calculating
trajectories  is a desirable feature,  although a time-consuming one.
Therefore, a motion should be calculated in a "compilation" step, and
executed at a later time, perhaps  repeatedly.  This leads to a clear
distinction between compile-time and runtime.

The user should  be able to demand that  a trajectory pass
through certain  intermediate points.  The primary  use of this is to
avoid collisions during the motion.   It
is  also useful  for specifying  complicated motions.

It is  necessary to test  for a wide range  of exceptional
conditions during  arm motion and to take  appropriate action as soon
as any  of them  occurs.   These conditions  could include  excessive
force being exerted,  excessive  closeness of the arms, completion of
some  related task  being done  independently by  other devices,   an
interrupt generated  by the  user, the arrival of a  certain time, or  a
temperature   sensor  reaching a  critical  point.   The  appropriate
actions might be to start up  a new concurrent process, to  terminate
something already  active, to  notify the user,   or  to file away  a
statistic  in a  table somewhere.   It is  also useful to  change the
nature of the test  during a motion,   if different segments  require
different types  of monitoring.   This concept can be  generalized to
include  the  modification  of  a  motion  during  its  execution  to
accomodate to changing  conditions. In any case,   it should be  easy
for the user to specify  exactly what is being tested, what the scope
of the test is  (that is,   when should it start  and when should  it
end), and what to do if it triggers.

Since locations are not known exactly during planning of a
trajectory,  there  should  be a  clear  distinction  between planned
values  and  runtime  values.    Planned  values  will  be  used  for
trajectory  calculation;  at runtime,    trajectories will  be
modified if necessary to account for any discrepancies.
The planned values are therefore a database on which trajectory
calculations are computed.  This database will often be
referred to as a world model.

Assembly tasks  require  that one  object  be affixed  to
another.   We  wish to  model  this by  having a  semantic attachment
between objects. When one moves, the second one should move (that is,
its   planning  value   should  be   modified)  accordingly.
Thus, the world model mentioned above should also include information
on attachments of objects, since planning values will be affected
by their existence.
The attachment  concept carries over to the  runtime system, which does
the equivalent modifications  of the actual  values.  This saves  the
user untold  bookkeeping operations to  determine where an  object is
after its base has been moved.

.NEWSS (THE RUNTIME SYSTEM,RUNTIME)

The calculation of trajectories is time-consuming but not
time-critical, and servoing of devices is time-critical but not
especially time-consuming.
It is intended that HAL be usable in a factory environment, with
perhaps continual execution of plans at many work stations.  These
two considerations lead us to the belief that
planning should occur on a large time-shared computer (like a PDP-10),
whereas execution of  plans
should  take place  under the  control of  a small  computer (like  a
PDP-11),  many  of  which  could be  distributed  in  the  work area.

The  runtime system  (which, as  just mentioned,  is
intended  to  reside  in a  minicomputer)  must  support simultaneous
executions of several processes.   Three basic types of process  have
been  identified: Interpreters,  which do  calculation,  servos,
each of which  controls one  joint  of  one  device, and monitors, which
continually examine  conditions.   These  must  be managed  in  some
(simple)  scheme  with guaranteed  response  for the
latter two types of process.

There must be enough information available at runtime  for
the proper modification  of trajectories immediately before  they are
executed.

The system must  be capable of using vision  and other yet
unpredictable forms of  feedback. Vision would be quite useful in
searching for objects  and testing  for adequacy of  assembly. It  is
conceivable that vision will be used for the servoing of an arm; this
implies that
vision must be in 
  the feedback loop during motions 
Other dynamic  feedback  (like
force-sensing wrists)  could make the  capabilities of the  arms much
greater in dealing with non-rigid materials like cloth or rope.  What
is needed is a way of specifying calls to these "external" devices so
that when they  become available,  they can be meshed into the system
without much difficulty.
.NEWSS (PROGRAMMING AIDS,PROGRAMMING AIDS)

A user should be able to compile a piece of code,  try
it on the spot, and delete or replace sections of previous code.

Error recovery facilities are very important.  A user should be
able to recover from errors discovered during any phase of debugging.
Similarly, production programs should be able to request operator
intervention where necessary and should (at least) be able to be
restarted at a convenient place after the problem is fixed.

The compiler itself should make a great number of semantic checks,
such as assuring that a proposed motion will not hit some object
(although this is a difficult problem which has not yet been
satisfactorily solved)  or that simultaneous independent motions are
not being requested for the same device.

The user should be given a wide choice of media for communication
with the system. For instance, status information from the arms and
other runtime devices should be available during the coding process
itself for the purpose of setting constants and for implementation of
"learning by showing" techniques.  Similarly, full use should be made
of available computer graphics hardware, both as a means for
depicting the compiler's planning model of various runtime states and
as another means of non-verbal input.

There should be a way to investigate the contents of the runtime
system, both variables and code,  in order to patch simple mistakes
discovered during the course of a production run.  This
feature would be especially useful for debugging the compiler.


.NEWSS (SOPHISTICATED USE OF WORLD MODEL INFORMATION,WORLD MODEL)

The compiler should be able to maintain a wide variety of information
about expected runtime states.  This includes not only object
attachments and variable planning values but also information like
the accuracy within which the planning value is known,  how heavy
objects are,  how many faces an object has on which it can rest,  how
wide the fingers of an arm should open to grasp it.  This information
may come from several sources, including explicit assertions by the
user, the output of  computer-aided design programs, and built-in 
knowledge about the system hardware.  

The system should provide a number of explicit mechanisms for using
this information, ranging from simple retrieval of data from the
compile-time model to conditional compilation facilities to produce
substantially different object programs, depending on the planning
information.  Such facilities allow the user to write a single piece
of code in some generality,  while avoiding the inefficiencies of
many needless runtime checks and the planning of useless trajectories
for cases that will never be executed.

The system should include enough domain-specific knowledge to allow
programs to be written in terms of common assembly operations, rather
than exclusively in terms of the detailed motions required.  At the
simplest level,  this involves provision of a library of common
assembly "macro-operations" that can be conditionally expanded to
perform particular subtasks.  Beyond this,  we would like an
interactive system that can take a "high level" description of an
assembly algorithm and fill in many of the detailed decisions
required to produce a consistent and efficient output program.  

The range of decisions required to 
convert from a high level description to an efficient output program
is quite broad, and many
of the processes involved cannot be modelled readily in terms of the
purely "local" mechanisms used in expanding library routines.  For
instance, a command like "put the engine block on the table in an
upright position" would require the system to examine future
operations on the engine block in selecting the exact orientation to
use.  Similarly, many operations produce side effects that make other
tasks either easier or harder.  For instance, inserting a pin into a
hole yields information about the exact location of the hole and,
hence, of the object into which the hole has been drilled.  If there
are a number of pins to be inserted, then it may be a good idea to
insert pins into the easier-to-locate holes first and then to use the
information so gained to help with the remaining insertions. (On the
other hand, such an ordering may very well make the actual insertions
more difficult because of obstructions to the hand). The system
should be able to use these sorts of considerations as it goes about
generating the output program.  

A user should be able to specify different parts of a task at various
levels of detail.  The system must be able to accept
explicit advice telling exactly how some particular subtask is to be
accomplished and then complete the program in a way that does not
conflict with those things that have been explicitly specified.  This
is especially important for early versions of HAL, which are not likely
to be very "smart" and will therefore require a fair
amount of explicit help.

The user should be able to describe the "intent" of a particular
piece of code, at least to the extent of specifying any (non-obvious)
prerequisites or updates to the world model.  This facility is
especially important for programs that mix both high and low-level
primitives. Similarly, the system should be able to show the user how
it is filling in the details to produce an output program, and why.
This is very important both for debugging and for explaining to the
user any requests for advice that it must make.
.NEWSEC (GENERAL SYSTEM OUTLINE,HARDWARE)

.NEWSS HARDWARE

	Currently  two  Stanford  Electric  Arms,   built  by  Victor
Scheinman [Scheinman], are available.  They are called YELLOW and BLUE.  Each has
six joints  and a hand  which can  open and  close.   The joints  are
controlled by  electrical motors; there  is feedback of  position and
velocity  for each joint.  The motor  drives are computed and sent to
the arm via a  digital-to-analog converter; the feedback  signals are
routed through an analog-to-digital converter back to the computer.

	There are two computer-controlled cameras. The 
computer can control the pan, tilt, focus, iris, filter, and zoom
(or lens turret) on each camera.

	Various others devices are designed and implemented as needed.
We use tools, jigs and special markings for several purposes:
to render a task possible (an example is the arm itself), to improve
efficiency (the mechanical screwdriver), and to overcome some of our
sensory and mechanical limitations (the screw dispenser).
Currently there is an electrically powered screwdriver, a pneumatic
vise, and an electrically controlled turntable.  The screwdriver can
be picked up by an arm and can operate in either direction over a range
of speeds.  The vise can be opened or closed and soon there will be
a way to servo it to a specified opening.  The computer can position
the turntable at any rotation (plus or minus .5 degrees).  As such
devices are built, they are interfaced to the A-to-D, the servo is
told how to control them, and the language is extended to include syntax
to describe how to use them.

	HAL  resides on two  computers: The PDP-10  for all planning,
and a PDP-11 for the execution of the plans.  The former is run  as a
timesharing computer  (under a  modified DEC  system); the  latter is
operated  in a  stand-alone mode under  the HAL  runtime system. Each
computer is capable of generating an interrupt in the  other, and the
PDP-10 has complete control over the PDP-11 console and unibus.


.NEWSS	SOFTWARE

	See {NEWFIG Overall system, FULL, sis←} for a picture of
the system.

	The SUPERVISOR  is the top level  of the system.   It runs on
the PDP-10 and provides an interface  between the user and the  other
parts  of  the  system:  1)  listening  to  the  user's  console  and
interpreting input  in a special command  language; 2) controling the
compiler, starting it  and relaying  its error messages  back to  the
user; 3) signalling the loader when it is necessary to place compiled
code into the PDP-11; 4) handling the runtime interface to the PDP11.
Each of these modules is discussed below.

	The USER sits at a console and makes requests  of HAL.  These
fall  into  several categories:  Compilation,  loading, execution  of
programs, debugging of  code, requesting of status information,  asking
for immediate arm motion, saving and restoring the state of the world
at safe points, requesting explanation of certain compiler decisions.

	The  COMPILER reads HAL programs  from files (or, optionally,
directly from the  user's console)  and produces load  modules.   The
compiler is divided into three  phases: The PARSER, the EXPANDER, and
the TRAJECTORY CALCULATOR. The compiler is discussed in detail in
{ssref com}.

	The LOADER  takes the load  modules prepared by  the compiler
and  enters them into the  PDP11 runtime system.   Address relocation
and linking are done  at this time. The loader  also sets up the  data
area  in the  runtime interface  in  the PDP-10;  this data  includes
output  strings,  procedure linkages,   and information necessary for
diagnostic purposes  during  runtime.   Loading is  often  done in  a
partially  incremental  fashion,     installing  new  code  following
previously loaded code.  

	The RUNTIME  INTERFACE is charged with  initiating the PDP-11
program,  fielding procedure  calls from  the running HAL  program to
PDP-10   procedures,  returning   values   from   these   procedures,
and fetching values from the
PDP-11 for debugging purposes.
The interface has the power to interrupt the execution of the program
and to modify the status of the runtime system, for example, by
patching in additional program, or modifying the values of some
variables.  This allows the user to control her program through
the timesharing computer.

	The RUNTIME SYSTEM is the set of programs which reside in the
PDP11.    This system  includes  kernel programs  for  time-slice cpu
sharing and  process  control   and  a  set of  dynamically  created
processes.    These are  of  three  basic  types: a)  An  INTERPRETER
examines the tables prepared by the compiler and executes the numeric
computations  requested.   When  a  move  is  to  be  started,    the
interpreter sprouts a servo for  each joint and waits until all these
servos terminate.  b) A SERVO handles the motion of one moving joint.
c)  A   CONDITION-MONITOR  repeatedly  examines   certain  conditions
(whatever the programmer  has specified).  If it should discover that
its condition  is  satisfied,   it  sprouts  an interpreter  to  take
appropriate action.   

	There is a database in the runtime system which stores the
current values of all active variables and the attachment relations
between them.  Whenever an interpreter needs a value, it is fetched
through this database.

	Facilities also exist for control of the runtime system
by means of the PDP-11 console.  The features that are available
include inspection of the status of all active and dormant processes
and the values of all variables, as well as the insertion of breakpoints
and the ability to insert, delete, or modify code.

The runtime  system also includes  routines for
communication  with the (PDP-10)  runtime  interface.   The runtime  system is
described in detail in {secref run} and Appendix II.